package 算法;

import java.util.ArrayList;
import java.util.List;

public class 前缀树 {
    public static void main(String[] args) {

        Trie trie = new Trie();
        trie.insert("as");
        trie.insert("ab");
        trie.insert("abcd");


        System.out.println(trie.search("as"));
        System.out.println(trie.search("abc"));
        System.out.println(trie.startsWith("abc"));
    }
}
class Trie {
    char value;
    List<Trie> root = new ArrayList<>();
    boolean flag = false; //表示是否为字符串的结束
    /** Initialize your data structure here. */
    public Trie() {

    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        if (word.length() < 1){
            return;
        }
        Trie temp;

        int i;
        for (i = 0; i < root.size(); i++) {
            temp = root.get(i);
            if(temp.value == word.charAt(0)){

                String str = word.substring(1);
                if(str.length() == 0){
                    temp.flag = true;
                }else
                    temp.insert(str);

                break;
            }

        }
        if(i >= root.size()){
            Trie trie = new Trie();
            trie.value = word.charAt(0);
            root.add(trie);

            String str = word.substring(1);
            if(str.length() == 0){
                trie.flag = true;
            }else
                trie.insert(str);
        }
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Trie trie = searchLastChar(word);
        return trie == null ? false:trie.flag;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        Trie trie = searchLastChar(prefix);
        return null == trie ? false:true;
    }
//    搜索prefix最后一个字符所在的结点，如果没有返回空
    private Trie searchLastChar(String prefix){
        if(prefix.length() == 0) return null;
        char c = prefix.charAt(0);
        for (Trie trie : root) {
            if(trie.value == c && prefix.length() == 1){
                return trie;
            }else if(trie.value == c){
                return trie.searchLastChar(prefix.substring(1));
            }
        }
        return null;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */